{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# LeetCode\n",
    "\n",
    "### 目录\n",
    "1. 两数之和(简单)\n",
    "2. 两数相加(中等)\n",
    "3. 两数相加(中等)\n",
    "4. 寻找两个正序数组的中位数\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "outputs": [],
   "source": [
    "import random"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.019065800Z",
     "start_time": "2023-08-31T05:10:44.920007Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### 1.两数之和\n",
    "\n",
    "给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。\n",
    "\n",
    "你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。\n",
    "\n",
    "你可以按任意顺序返回答案。"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "outputs": [],
   "source": [
    "def twoSum(nums: list[int], target: int) -> list[int]:\n",
    "    for a in range(len(nums)):\n",
    "        for b in range(a + 1, len(nums)):\n",
    "            if nums[a] + nums[b] == target:\n",
    "                return [a, b]\n",
    "twoSum([3, 2, 4], 6)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-10-14T06:19:40.816968Z",
     "start_time": "2024-10-14T06:19:40.803962Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### 2. 两数相加\n",
    "\n",
    "给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。\n",
    "\n",
    "请你将两个数相加，并以相同形式返回一个表示和的链表。\n",
    "\n",
    "你可以假设除了数字 0 之外，这两个数都不会以 0 开头。\n",
    "\n",
    "示例\n",
    "```\n",
    "输入：l1 = [2,4,3], l2 = [5,6,4]\n",
    "输出：[7,0,8]\n",
    "解释：342 + 465 = 807.\n",
    "```"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "题目给出的数据结构的定义"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.021073300Z",
     "start_time": "2023-08-31T05:10:44.943134800Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "这里给出一个打印结果来验证答案的方法"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [],
   "source": [
    "def print_res(res: ListNode):\n",
    "    str = \"\"\n",
    "    while True:\n",
    "        str += res.val.__str__()\n",
    "        if res.next is not None:\n",
    "            res = res.next\n",
    "        else:\n",
    "            break\n",
    "    print(\"res: \", str)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.022063300Z",
     "start_time": "2023-08-31T05:10:44.959071600Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "这是我自己写的一个非递归的函数"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "outputs": [],
   "source": [
    "def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:\n",
    "    res = ListNode(0, None)  # 结果的头节点\n",
    "    sum = l1.val + l2.val\n",
    "    if sum >= 10:\n",
    "        res.val = sum % 10\n",
    "        flag = 1\n",
    "    else:\n",
    "        res.val = sum\n",
    "        flag = 0\n",
    "    end = res\n",
    "    next_node = ListNode()\n",
    "    res.next = next_node\n",
    "    # 满足以下两个条件则跳出循环: 1.两个链表都走到末尾 2.没有进位\n",
    "    while l1.next or l2.next or (flag == 1):\n",
    "        l1 = l1.next if l1.next else ListNode()\n",
    "        l2 = l2.next if l2.next else ListNode()\n",
    "        # 判断上一位是否进位\n",
    "        if flag == 1:\n",
    "            sum = l1.val + l2.val + 1\n",
    "        else:\n",
    "            sum = l1.val + l2.val\n",
    "\n",
    "        # 求和\n",
    "        if sum >= 10:\n",
    "            next_node.val = sum % 10\n",
    "            flag = 1\n",
    "        else:\n",
    "            next_node.val = sum\n",
    "            flag = 0\n",
    "\n",
    "        end = next_node\n",
    "        next_node.next = ListNode(0, None)\n",
    "        next_node = next_node.next\n",
    "\n",
    "    end.next = None\n",
    "    return res"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.022063300Z",
     "start_time": "2023-08-31T05:10:44.976074800Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "测试用例"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "res:  708\n",
      "1.62 µs ± 397 ns per loop (mean ± std. dev. of 7 runs, 30 loops each)\n"
     ]
    }
   ],
   "source": [
    "# 测试用例1\n",
    "l1 = ListNode(2, ListNode(4, ListNode(3)))\n",
    "l2 = ListNode(5, ListNode(6, ListNode(4)))\n",
    "print_res(addTwoNumbers(l1, l2))\n",
    "%timeit -n 30 addTwoNumbers(l1, l2)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.022063300Z",
     "start_time": "2023-08-31T05:10:44.990070400Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "res:  0\n",
      "596 ns ± 30.4 ns per loop (mean ± std. dev. of 7 runs, 30 loops each)\n"
     ]
    }
   ],
   "source": [
    "# 测试用例2\n",
    "l1 = ListNode(0)\n",
    "l2 = ListNode(0)\n",
    "print_res(addTwoNumbers(l1, l2))\n",
    "%timeit -n 30 addTwoNumbers(l1, l2)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.053014300Z",
     "start_time": "2023-08-31T05:10:45.005073600Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "res:  89990001\n",
      "4.1 µs ± 180 ns per loop (mean ± std. dev. of 7 runs, 300 loops each)\n"
     ]
    }
   ],
   "source": [
    "# 测试用例3\n",
    "l1 = ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))))\n",
    "l2 = ListNode(9, ListNode(9, ListNode(9, ListNode(9))))\n",
    "print_res(addTwoNumbers(l1, l2))\n",
    "%timeit -n 300 addTwoNumbers(l1, l2)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.055013400Z",
     "start_time": "2023-08-31T05:10:45.020072700Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "res:  18\n",
      "1.09 µs ± 59.5 ns per loop (mean ± std. dev. of 7 runs, 30 loops each)\n"
     ]
    }
   ],
   "source": [
    "# 测试用例4\n",
    "l1 = ListNode(1, ListNode(8))\n",
    "l2 = ListNode(0)\n",
    "print_res(addTwoNumbers(l1, l2))\n",
    "%timeit -n 30 addTwoNumbers(l1, l2)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.112164900Z",
     "start_time": "2023-08-31T05:10:45.036071200Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "这是和我类似的优化过的算法, 速度上优化了25%左右\n",
    "主要解决了几个问题:\n",
    "1. 为了记录头结点的值, 首次计算不能直接进入循环的问题.\n",
    "解决方法是, 创建了一个虚拟头节点, 仅代表一个指针, 类似于数据结构中链表的head指针, 所以dummy节点值为-1.\n",
    "这也解决了我代码中频繁更换end节点以截取最后一个节点的问题\n",
    "2. `divmod()`函数返回一个tuple (x//y, x%y), 减少了代码的行数, 使用原生函数可能能较大提高运算的速度\n",
    "3. `if sth is not None:` 这个判断 可以直接简化为 `sth`\n",
    "4. 为了避免参数和变量的混淆, 最好将参数直接在函数内赋值`p1, p2 = l1, l2`\n",
    "5. 从`val = carry`到`if p1:`和`if p2:` 这三个代码块是从计算机本质的角度思考, 而不是从人的直觉的角度思考, 应学会这样的思考方法"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "outputs": [],
   "source": [
    "def addTwoNumbers_op(l1: ListNode, l2: ListNode) -> ListNode:\n",
    "    p1, p2 = l1, l2\n",
    "    # 虚拟头结点（构建新链表时的常用技巧）\n",
    "    dummy = ListNode(-1)\n",
    "    # 指针 p 负责构建新链表\n",
    "    p = dummy\n",
    "    # 记录进位\n",
    "    carry = 0\n",
    "    # 开始执行加法，两条链表走完且没有进位时才能结束循环\n",
    "    while p1 or p2 or carry:\n",
    "        # 先加上上次的进位\n",
    "        val = carry\n",
    "        if p1:\n",
    "            val += p1.val\n",
    "            p1 = p1.next\n",
    "        if p2:\n",
    "            val += p2.val\n",
    "            p2 = p2.next\n",
    "        # 处理进位情况\n",
    "        carry, val = divmod(val, 10)\n",
    "        # 构建新节点\n",
    "        p.next = ListNode(val)\n",
    "        p = p.next\n",
    "    # 返回结果链表的头结点（去除虚拟头结点）\n",
    "    return dummy.next"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.123076900Z",
     "start_time": "2023-08-31T05:10:45.051005900Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "res:  89990001\n",
      "2.93 µs ± 122 ns per loop (mean ± std. dev. of 7 runs, 300 loops each)\n"
     ]
    }
   ],
   "source": [
    "# 测试用例3\n",
    "l1 = ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))))\n",
    "l2 = ListNode(9, ListNode(9, ListNode(9, ListNode(9))))\n",
    "print_res(addTwoNumbers_op(l1, l2))\n",
    "%timeit -n 300 addTwoNumbers_op(l1, l2)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.124081100Z",
     "start_time": "2023-08-31T05:10:45.067070100Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "速度最快的方法采用递归的方法\n",
    "运算顺序:\n",
    "如计算 [2,4,3] + [5,6,4]\n",
    "则第一次进入函数 2 + 5 = 7 则l1 = [7,4,3], l2一直不变\n",
    "第二次进入函数 l1 的第二个节点值为10, 所以第10行的条件, 将进位1和l1的第三个节点作为参数第三次进入函数\n",
    "第三次进入函数 第9行 将进位1加到l1的第三位并赋值给l1的第三个节点l1 = [7, x ,4]\n",
    "此时返回到第二次进入函数的`l1.val %= 10`, l1=[7,0,4]\n",
    "此时执行到第二次进入函数的`l1.next = addTwoNumbers_rec(l1.next, l2.next)`, 第四次进入函数\n",
    "第四次执行函数的参数l1.next = l1[3], l2.next = l2[3]; 执行到第9行, 此时l1 = [7,0,8]; 执行到第14行, 由于l1和l2的next均为空, 所以第五次参数为None, None, 那么l1.next即为空\n",
    "执行完毕, l1即为最终解"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "outputs": [],
   "source": [
    "def addTwoNumbers_rec(l1: ListNode, l2: ListNode) -> ListNode:\n",
    "    # l1为空 则返回l2\n",
    "    if not l1:\n",
    "        return l2\n",
    "    # l2为空 则返回l1\n",
    "    if not l2:\n",
    "        return l1\n",
    "\n",
    "    l1.val += l2.val  # 将两数相加，赋值给 l1 节点\n",
    "    if l1.val >= 10:\n",
    "        l1.next = addTwoNumbers_rec(ListNode(l1.val // 10), l1.next)\n",
    "        l1.val %= 10\n",
    "\n",
    "    l1.next = addTwoNumbers_rec(l1.next, l2.next)\n",
    "    return l1"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.125050800Z",
     "start_time": "2023-08-31T05:10:45.083013600Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "res:  89990001\n",
      "2.69 µs ± 44 ns per loop (mean ± std. dev. of 7 runs, 300 loops each)\n"
     ]
    }
   ],
   "source": [
    "# 测试用例3\n",
    "l1 = ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))))\n",
    "l2 = ListNode(9, ListNode(9, ListNode(9, ListNode(9))))\n",
    "print_res(addTwoNumbers_op(l1, l2))\n",
    "%timeit -n 300 addTwoNumbers_op(l1, l2)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.126005700Z",
     "start_time": "2023-08-31T05:10:45.098139500Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### 3. 无重复字符的最长子串"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "给定一个字符串 s ，请你找出其中不含有重复字符的 *最长子串* 的长度。\n",
    "\n",
    "输入: s = \"abcabcbb\"\n",
    "输出: 3\n",
    "解释: 因为无重复字符的最长子串是 \"abc\"，所以其长度为 3。\n",
    "\n",
    "输入: s = \"bbbbb\"\n",
    "输出: 1\n",
    "解释: 因为无重复字符的最长子串是 \"b\"，所以其长度为 1。\n",
    "\n",
    "输入: s = \"pwwkew\"\n",
    "输出: 3\n",
    "解释: 因为无重复字符的最长子串是 \"wke\"，所以其长度为 3。\n",
    "     请注意，你的答案必须是 子串 的长度，\"pwke\" 是一个子序列，不是子串。"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "我的答案"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "outputs": [],
   "source": [
    "def lengthOfLongestSubstring(s: str) -> int:\n",
    "    length = 0\n",
    "    for i in range(len(s)):\n",
    "        char_set = set()\n",
    "        for j in range(i, len(s) + 1):\n",
    "            if j == len(s) or s[j] in char_set:\n",
    "                if length < len(char_set):\n",
    "                    length = len(char_set)\n",
    "                break\n",
    "            char_set.add(s[j])\n",
    "\n",
    "    return length"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.140014700Z",
     "start_time": "2023-08-31T05:10:45.116095300Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "outputs": [
    {
     "data": {
      "text/plain": "18"
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"dsHEIDfZxDfXPdgC9PusaNmBuTS3lW4zfWxr1P8OwYzLV0hBZpwYSnY40qTBs6hiT1x2TQZOAwRScbKgGGprmRsozozarBxHELoF\"\n",
    "lengthOfLongestSubstring(s)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.205205700Z",
     "start_time": "2023-08-31T05:10:45.130016Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "126 µs ± 3.99 µs per loop (mean ± std. dev. of 7 runs, 30 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 30 lengthOfLongestSubstring(s)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.216039400Z",
     "start_time": "2023-08-31T05:10:45.146013500Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "在时间效率上优化的算法"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "outputs": [],
   "source": [
    "def lengthOfLongestSubstring_opt(s: str) -> int:\n",
    "    if not s:\n",
    "        return 0\n",
    "    max_len = 0\n",
    "    start = 0  # 表示滑动窗口开始的位置\n",
    "    for win_size in range(1, len(s)):\n",
    "        c = s[win_size]\n",
    "        win_str = s[start:win_size]  #滑动窗口的尺寸\n",
    "        if c in win_str:\n",
    "            # 用max()函数来替代if语句\n",
    "            max_len = max(max_len, win_size - start)\n",
    "            start += win_str.index(c) + 1\n",
    "    return max(max_len, len(s) - start)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.216039400Z",
     "start_time": "2023-08-31T05:10:45.192066500Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11.8 µs ± 163 ns per loop (mean ± std. dev. of 7 runs, 30 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 30 lengthOfLongestSubstring_opt(s)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.239006400Z",
     "start_time": "2023-08-31T05:10:45.208040700Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "可以看到我的代码虽然在结构上更加简便, 但是在运算速度上优化算法提升了非常大, 提升了90%.\n",
    "\n",
    "原因:\n",
    "\n",
    "这道题主要用到思路是：滑动窗口\n",
    "\n",
    "比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。\n",
    "所以，我们要移动这个队列\n",
    "\n",
    "我们只要把队列的左边的元素移出就行了，直到满足题目要求\n",
    "\n",
    "在滑动窗口思想下, 时间复杂度为O(n), 而我使用的方法则为O(n^2)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### 4.寻找两个正序数组的中位数"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。\n",
    "\n",
    "算法的时间复杂度应该为 O(log (m+n)) 。\n",
    "\n",
    "\n",
    "示例 1：\n",
    "\n",
    "输入：nums1 = [1,3], nums2 = [2]\n",
    "输出：2.00000\n",
    "解释：合并数组 = [1,2,3] ，中位数 2\n",
    "\n",
    "\n",
    "\n",
    "示例 2：\n",
    "\n",
    "输入：nums1 = [1,2], nums2 = [3,4]\n",
    "输出：2.50000\n",
    "解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "outputs": [
    {
     "data": {
      "text/plain": "3131"
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [x for x in range(1, 10000)]\n",
    "l1 = sorted(random.sample(l, 6868))  # 从l中选择8686个元素作为一个新的列表返回, 抽样随机独立且为不放回抽样, 所以新生成的列表中不会又重复的元素\n",
    "l2 = [x for x in l if x not in l1]\n",
    "len(l2)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.508093900Z",
     "start_time": "2023-08-31T05:10:45.221073200Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "outputs": [],
   "source": [
    "# 题目难度在于要求时间复杂度log(m+n), 但这个函数需要排序, 复杂度明显大于要求\n",
    "def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:\n",
    "    nums = nums1 + nums2\n",
    "    nums.sort()\n",
    "    length = len(nums)\n",
    "    if length % 2 == 1:\n",
    "        return nums[(length - 1) // 2]\n",
    "    else:\n",
    "        return (nums[length // 2] + nums[length // 2 - 1]) / 2"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.520748400Z",
     "start_time": "2023-08-31T05:10:45.505160800Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "outputs": [
    {
     "data": {
      "text/plain": "5000"
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findMedianSortedArrays(l1, l2)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.564692800Z",
     "start_time": "2023-08-31T05:10:45.520748400Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "68.9 µs ± 4.56 µs per loop (mean ± std. dev. of 7 runs, 30 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 30 findMedianSortedArrays(l1, l2)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.575676Z",
     "start_time": "2023-08-31T05:10:45.536709Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "优化算法\n",
    "\n",
    "将问题转换为第k小数的解法, 即:\n",
    "> 假设两个数组合并为一个包含n个元素有序的数组, 第k小的数就是中位数, 其中k=n/2\n",
    "\n",
    "对于两个有序的数组, 想要找到第k小的数, 一个很自然的想法就是折半删除: 将两个数组每次对半分, 并保留那个包含中位数的部分, 其余的删除.\n",
    "\n",
    "例如: 一下这个例子, 上下为两个数组, 总计共9个元素, 其中k为第5个元素, k/2=2, 即选取两个数组的第2个元素, 此时比较两个指针位置元素的大小, 并删除较小的部分.\n",
    "\n",
    "![1](assets/img.png)\n",
    "\n",
    "删除2和3后, 剩余的元素如果合并为一个大的数组, 则如图所示\n",
    "\n",
    "![2](assets/img_4.png)\n",
    "\n",
    "此时即求这个大数组中的第3小的数, 即k=3 k/2=1, 指针指向两个数组的第1个元素比较大小, 删除元素1\n",
    "\n",
    "![3](assets/img_1.png)\n",
    "\n",
    "此时大数组的状态为\n",
    "\n",
    "![3](assets/img_5.png)\n",
    "\n",
    "以此类推, k=2 k/2=1, 删除4\n",
    "\n",
    "![3](assets/img_2.png)\n",
    "\n",
    "k=1 k/2=0, 此时所有小于中位数的元素都被删除了, 所以选取较小的那一个即为中位数, 由此得中位数为5\n",
    "\n",
    "![3](assets/img_6.png)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "outputs": [],
   "source": [
    "def findMedianSortedArrays_opt(nums1: list, nums2: list) -> float:\n",
    "    def get_k_min(nums1, start1, end1, nums2, start2, end2, k):\n",
    "        remain1 = end1 - start1 + 1\n",
    "        remain2 = end2 - start2 + 1\n",
    "        if remain1 == 0:\n",
    "            return nums2[start2 + k - 1]\n",
    "        if remain2 == 0:\n",
    "            return nums1[start1 + k - 1]\n",
    "        if k == 1:\n",
    "            return min(nums1[start1], nums2[start2])\n",
    "        i = start1 + min(remain1, k // 2) - 1\n",
    "        j = start2 + min(remain2, k // 2) - 1\n",
    "        if nums1[i] <= nums2[j]:\n",
    "            return get_k_min(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1))\n",
    "        else:\n",
    "            return get_k_min(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1))\n",
    "\n",
    "    m, n = len(nums1), len(nums2)\n",
    "    mid1 = (m + n + 1) // 2\n",
    "    mid2 = (m + n + 2) // 2\n",
    "    a = get_k_min(nums1, 0, m - 1, nums2, 0, n - 1, mid1)\n",
    "    b = get_k_min(nums1, 0, m - 1, nums2, 0, n - 1, mid2)\n",
    "    return (a + b) / 2"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.596813800Z",
     "start_time": "2023-08-31T05:10:45.566689200Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "outputs": [
    {
     "data": {
      "text/plain": "5000.0"
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findMedianSortedArrays_opt(l1, l2)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.627721800Z",
     "start_time": "2023-08-31T05:10:45.583674400Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13.8 µs ± 814 ns per loop (mean ± std. dev. of 7 runs, 30 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 30 findMedianSortedArrays_opt(l1, l2)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-08-31T05:10:45.628729200Z",
     "start_time": "2023-08-31T05:10:45.603699300Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "那么为什么每次删除的元素均是小于中位数的元素呢?\n",
    "\n",
    "这个问题可以转换为新的问题, 即: 两个有序数组, 元素总数为n, 不论两个有序数组是怎样分布的, 两个指针所指向的较小的元素的一定小于中位数\n",
    "\n",
    "由下图可以看到, 在一个有序数组中, 大于等于中位数元素的个数为 $n - k + 1$\n",
    "\n",
    "我们假设指针指向的较小元素为a, 较大元素为b\n",
    "\n",
    "那么我们只需要证明: $\\text{大于a的元素个数} \\ge  n - k + 1$\n",
    "\n",
    "![2](assets/img_7.png)\n",
    "\n",
    "大于a的元素个数如下图中红框标注出来的元素:\n",
    "\n",
    "![2](assets/img_8.png)\n",
    "\n",
    "\n",
    "指针的位置即为 $\\frac{k}{2}$ , 大于a的元素个数就可以写为 $ n - (\\frac{k}{2} + \\frac{k}{2} -1)$\n",
    "\n",
    "即 \n",
    "$$ n - (k/2 + k/2 - 1) \\ge  n - k + 1 \\\\\n",
    "k \\ge  k/2 *2 \\\\\n",
    " 当 k 为偶数时, k \\ge  k \\\\\n",
    " 当 k 为奇数是, k \\ge  k - 1\n",
    "$$"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": "",
   "metadata": {
    "collapsed": false
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
